Beyond Descriptive Modelling of Network Degrees: Tail-Realistic Preferential Attachment

The scale-free debate

A network is scale-free if the tail of the degree distribution follows a power-law.

\[ \Pr(K>k) = \bar F(k) \sim k^{-\gamma} \]

Modelling the degrees

Mixture Model

Using this model @Lee24 found that networks often have a heavy tail but not quite as heavy as implied by the body.

Why care about scale-freeness?

Many use scale-freeness of a network to justify the mechanics behind the network’s growth.

Preferential Attachment (rich-get-richer) \(\Rightarrow\) Power-law degree distribution

Aims

• Propose a flexible tail-realisitic model for network degrees
• Obtain information about network growth from degrees alone

Preferential Attachment

Results in a power-law degree distribution

\[ \bar F(k)\sim k^{-2} \]

General Preferential Attachment

Branching Process

Consider a CTBP \(\zeta(t)\) driven by Markovian pure birth process

\[ \Pr(\zeta(t+\text{d}t) = k+1 | \zeta(t) =k) = b(k) \text{d}t + o(\text{d}t) \]

Construct tree \(\Upsilon(t)\) determined by \(\zeta(t)\), where each node in the tree has birth rate \(b(\text{deg}(x,\Upsilon(t)))\).

Then the tail of the limiting degree distribution is:

\[ \bar F(k) = \lim_{t\rightarrow \infty} \frac{\sum_{x\in\Upsilon(t)}\mathbb I \left\{\text{deg}(x, \Upsilon(t))_{\downarrow x}>k\right\}}{ \sum_{x\in\Upsilon(t)} \mathbb I \left\{\text{deg}(x, \Upsilon(t))_{\downarrow x}\ge 0\right\}\right\}} \]

Now applying a result from [Rudas et al.]

Rudas result

For a characteristic \(\phi\) of the tree \(\Upsilon(t)\):

\[ \lim_{t\rightarrow\infty} \frac{1}{\left|\Upsilon(r)\right|}\sum_{x\in\Upsilon(t)}\phi(\Upsilon(t)_{\downarrow x}) = \lambda^* \int_0^\infty e^{-\lambda^*}\mathbb E \left[\phi(\Upsilon(t))\right]\text{d}t \]

\[ \bar F(k) = \frac{\int_0^\infty e^{-\lambda^*t}\mathbb I \left\{\text{deg}(x, \Upsilon(t))_{\downarrow x}>k\right\}\text{d}t }{\int_0^\infty e^{-\lambda^* t} \text{d}t} = \prod_{i=0}^k \frac{b(i)}{\lambda^* + b(i)},\quad k=0,1,2, \ldots \]

Studying the tail

We want to pay careful attention to the extreme values

Studies of empirical degrees often use methods from continuous extremes

As this is a discrete distribution we need some new machinery.

Continuous Extremes Recap

Maximum Domains of Attraction

Discrete Extremes

[Shimura] uses the following quantity to categorise discrete distributions \[ \Omega(F, k) = \left(\log \frac{\bar F(k+1)}{ \bar F(k+2)}\right)^{-1} - \left(\log \frac{\bar F(k)}{ \bar F(k+1)}\right)^{-1} \]

Analysing GPA degrees

Now we can use the limiting survival function of a GPA model to show that:

\[ \lim_{k\rightarrow\infty} \Omega(F,k)= \begin{cases} \lim_{k\rightarrow \infty}\frac{b(k+1)-b(k)}{\lambda^*}, &\text{when } b(k) \rightarrow \infty\\ 0, &\text{otherwise} \end{cases} \]

Examples

What we have learned so far.

\[ \lim_{k\rightarrow\infty} \Omega(F,k)= \begin{cases} \lim_{k\rightarrow \infty}\frac{b(k+1)-b(k)}{\lambda^*}, &\text{when } b(k) \rightarrow \infty\\ 0, &\text{otherwise} \end{cases} \]

• Empirical degree distributions are heavy-tailed but exhibit more nuanced behaviour than obtained by BA model
• For degree distribution to be heavy tailed and be the result of a GPA model, preference must be eventually “linear” like in the BA model

Constructing a new preference function

We require something that is eventually linear but is flexible enough for real networks

Shape of degree distribution

Tail behaviour

% heat map plot

\[ \lim_{k\rightarrow\infty} \Omega(F, k) = \beta / \lambda^*, \qquad \lim_{k\rightarrow\infty} \bar F(k+1)/ \bar F(k) = 1 \]

All limiting degree distributions produces by this model are Frechet with tail-index \(\lambda^*/\beta\).

Connection to Existing Method

We can find that: \[ \bar F(k) \begin{cases} =\prod_{i=0}^{k}\frac{i^\alpha + \varepsilon}{\lambda^*+i^\alpha + \varepsilon},&k\le k_0,\\ \approx \left(\prod_{i=0}^{k_0}\frac{i^\alpha + \varepsilon}{\lambda^* + i^\alpha + \varepsilon}\right)\left(\frac{\beta(k-k_0)}{k_0^{\alpha}+\varepsilon+\beta} + 1\right)^{-\lambda^{*}/\beta},&k > k_0, \end{cases} \]

that is, conditional degree distribution is approximated by:

\[ \text{IGP}\left(\frac{\beta}{\lambda^*}, \frac{k_0^\alpha + \varepsilon+\beta}{\lambda^*},k_0\right) \]

a distribution used by [Lee] for modelling network degrees.

Unfortunately we can’t go from the IGP fit to the model parameters.

Simulation Study - set up

1. Simulate networks
2. Use likelihood to fit model
3. Recover parameters

The simulated data

• 100,000 nodes
• 36 parameter combinations
• \(k_0\) fixed at \(20\)
• Only using final degrees

The likelihood

\[ \begin{aligned} L(\pmb n | \pmb \theta,l) = &\left(\frac{\lambda^*}{\lambda^*+\varepsilon}\right)^{n_0}\left(\prod_{j=l}^{k_0-1}\frac{j^\alpha +\varepsilon}{\lambda^* + j^\alpha +\varepsilon}\right)^{\left(\sum_{i\ge k_0}n_{i}\right)} \\ &\times \prod_{l \le i<k_0}\left(\frac{\lambda^*}{\lambda^* +i^\alpha + \varepsilon } \prod_{j=l}^{k_0-1}\frac{j^\alpha + \varepsilon}{\lambda^* + j^\alpha + \varepsilon}\right)^{n_i}\\ &\times \prod_{i\ge k_0}\left(\frac{\text{B}(i-k_0 + (k_0^\alpha + \varepsilon)/\beta,1+\lambda^*/\beta)}{\text{B}((k_0^\alpha + \varepsilon)/\beta,\lambda^*/\beta)}\right)^{n_i}, \end{aligned} \]

Priors

\[\begin{align*} \alpha&\sim \text{Gamma}(1,0.01),\\ \beta &\sim \text{Gamma}(1,0.01),\\ k_0 &\sim \text{U}(1,10,000),\\ \varepsilon &\sim \text{Gamma(1,0.01)}, \end{align*}\]

Now we use an adaptive Metroplis-Hastings to obtain posterior samples

Model fits

%show model fitting the degree distribution well

The results

\(\alpha\) posterior

The results

\(\varepsilon\) posterior

The results

\(k_0\) posterior

The results

\(\beta\) posterior

Real Data

Fitting to Real Data

Bonus Information

Key Results

• Characterisation of degree distribution from preference function
  • Eventually linear \(\rightarrow\) Frechet (heavy tail)
  • Sublinear and unbounded \(\rightarrow\) Gumbel (light tail)
  • Bounded \(\rightarrow\) recoverable to Gumbel (light tail)
• Proposed preference function gives tail-realistic degree distributions
• Parameters recovered from degrees alone in simulated networks
• Can learn about real networks growth from snapshot of degrees

Limitations and Future work

• Theory based on trees, which real networks rarely are

• Only consider degrees in the snapshot

• Assume a fairly restrictive model (pure birth)

• Look beyond just the degrees

• Incorporate more complex behaviour into the growth model

• Extend theory beyond that of trees

Thank you